/**
 * @param {number[]} nums
 * @return {number}
 */
// 动态规划
// 以i为结尾的最大连续子数组和
// 当前状态只与前面状态有关（可以压缩）
var maxSubArray = (nums) => {
  let len = nums.length
  const dp = new Array(len).fill(0)
  dp[0] = nums[0]
  let ans = nums[0]
  for(let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
    ans = Math.max(dp[i], ans)
  }
  return ans
}
var maxSubArray = (nums) => {
  let len = nums.length
  let dp = nums[0]
  let ans = nums[0]
  for(let i = 1; i < len; i++) {
    dp = Math.max(dp + nums[i], nums[i])
    ans = Math.max(dp, ans)
  }
  return ans
}
var maxSubArray = (nums) => {
  let len = nums.length
  const dp = new Array(len).fill(0)
  dp[0] = nums[0]
  let ans = nums[0]
  for(let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
    ans = Math.max(dp[i], ans)
  }
  return ans
}
// 动态规划压缩空间
var maxSubArray = function(nums) {
  let max = nums[0]
  let sum = 0
  for(let i = 0; i < nums.length; i++) {
     sum += nums[i]
     max = Math.max(sum, max)
     if(sum < 0) sum = 0
  }
  return max
};